/*
struct BinaryTreeNode {
    int m_nValue;
    struct BinaryTreeNode *m_pLeft;
    struct BinaryTreeNode *m_pRight;
    struct BinaryTreeNode *m_pParent;
    BinaryTreeNode(int x) :m_nValue(x), m_pLeft(NULL), m_pRight(NULL), m_pParent(NULL) {
        
    }
};
*/

/****************递归*************************/
BinaryTreeNode* GetNextWithoutRight(BinaryTreeNode* pNode) {
	//若父结点为空，则代表该结点是根结点或者由右子树端回退到根结点
	if (!pNode->m_pParent) return NULL;
	//若该结点位于父类左子树
	if (pNode == pNode->m_pParent->m_pLeft) {
		return pNode->m_pParent;
	}
	else if (pNode == pNode->m_pParent->m_pRight) {
		return GetNextWithoutRight(pNode->m_pParent);
	}
	else {
		return NULL;
	}
}

BinaryTreeNode* GetNext(BinaryTreeNode* pNode)
{
	if (pNode == NULL) return NULL;

	//情况一：若该结点右子树不为空，则根据其右结点是否有左子树判断中序遍历的下一个结点
	//情况二：若该结点右子树为空,则使用递归找到是其父节点的左结点的结点
	if (pNode->m_pRight) {
		if (pNode->m_pRight->m_pLeft) {
			return  pNode->m_pRight->m_pLeft;
		}
		else {
			return pNode->m_pRight;
		}
	}
	else {
		//递归
		return GetNextWithoutRight(pNode);
	}
}

/****************无需使用递归*************************/
BinaryTreeNode* GetNext(BinaryTreeNode* pNode)
{
	if (pNode == NULL) return NULL;

	//情况一：若该结点右子树不为空，则根据其右结点是否有左子树判断中序遍历的下一个结点
	//情况二：若该结点右子树为空,则可用while()循环找到是其父节点的左结点的结点
	if (pNode->m_pRight) {
		if (pNode->m_pRight->m_pLeft) {
			return  pNode->m_pRight->m_pLeft;
		}
		else {
			return pNode->m_pRight;
		}
	}
	else {
		BinaryTreeNode* pCurrent = pNode;
		BinaryTreeNode* pParent = pNode->m_pParent;
		while ((pParent) && (pCurrent == pParent->m_pRight)) {
			pCurrent = pCurrent->m_pParent;
			pParent = pCurrent->m_pParent;
		}
		return pParent;
	}
}